#include <iostream>

using std::cout;
using std::endl;

void merge(int* a,int p,int q,int r) {
	int len_l = q-p+1;
	int len_r = r-q;
	
	int* array_l = (int*) malloc(sizeof(int)*(len_l+1));
	array_l[len_l] = 100;
	for(int i=p;i<=q;i++) {
		array_l[i-p] = a[i];
	}
	int* array_r = (int*) malloc(sizeof(int)*(len_r+1));
	array_r[len_r] = 100;
	for(int i=q+1;i<=r;i++) {
		array_r[i-q-1] = a[i];
	}
	int il = 0;
	int ir = 0;
	for(int i=p;i<=r;i++) {
		if(array_l[il]<=array_r[ir]){
			a[i] = array_l[il];
			il++;
		}
		else {
			a[i] = array_r[ir];
			ir++;
		}
	}
}

void merge_sort(int* a,int p,int r) {
	if(p<r) {
		int q = (p+r)/2;
		merge_sort(a,p,q);
		merge_sort(a,q+1,r);
		merge(a,p,q,r);
	}
}

int main() {
	int a[] = {9,0,5,2,4,6,1,3,8,7};
	merge_sort(a,0,9);
	
	for(int i=0;i<10;i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	
	return 0;
}